package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/21 8:19
 * @description <p>和为 k 的子数组</p>
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：输入一个整数数组和一个整数 k，请问数组中有多少个数字之和
 * 等于 k 的连续子数组？例如，输入数组[1, 1, 1]，k 的值为 2，有 2 个连续子
 * 数组之和等于 2。
 */
public class toOffer2_3_10 {
    public static void main(String[] args) {
        int nums[] = {1, 1, 1};
        System.out.println(subarraySum(nums, 2));
    }

    //暴力解法
    public static int subarraySum1(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            sum += nums[i];
            //因为下面for循环设置的的是j=i+1，所以存在一个缺陷：如果数组里的最后一个数也符合条件的话，是取不到的
            //如果nums数组的最后一个值符合条件，那么就让result+1
            if (nums[i] == k) {
                result += 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    result += 1;
                }
            }
        }

        return result;
    }

    /**
     * 使用前缀和
     * 首先要明确前缀和的概念，第 i 个数的前缀和也就是从nums[0]一直加到nums[i-1]。
     * 那么我所有的连续子数组就可以使用前缀和来表示，比如 i -> j的连续数组的和就等于 preSum[j] - preSum[i]
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        //map里key为前缀和，v为对应的前缀和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        //初始化map
        map.put(0, 1);
        int sum = 0;
        int result = 0;

        //遍历nums数组并添加前缀和
        for (int num : nums) {
            sum += num;
            //判断map里有没有对应的k为sum-k的前缀和，有就让result+1
            if (map.containsKey(sum - k)) {
                result += map.get(sum - k);
            }
            //添加前缀和
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return result;
    }

}